Crossbar switches are used in digital systems to provide communication between sources of data and sinks of data. A typical crossbar environment is shown in FIG. 1, wherein N sources of information and N sinks of information are shown connected by an N by N crossbar switch. At any given time, a data source may establish a connection to a data sink for data transmission. Connections may be terminated by either the source or the sink, and the crossbar switch allows several concurrent connections to operate. A crossbar switch should have the ability to establish a connection between one source and multiple sinks.
Crossbar switches see uses in many computer applications. In some parallel computers which share memories, the processors are placed on one side of a crossbar switch (acting as sources) and memory banks are placed on the other side (acting as sinks). As such, the switch allows any processor to access any memory bank and further allows multiple processors/memory bank connections to be in operation simultaneously. In such systems, one processor often wishes simultaneous access to data in several memory banks and as a result, the crossbar switch must support the notion of one source connecting to multiple sinks.
Crossbar switches are also found in nodes of distributed memory, parallel computer systems. In such systems, each node is directly connected to several other nodes, using data links. A crossbar switch at each node allows a message arriving along an inbound data link to be sent out over any set of outbound data links. In such systems, the initiating node merely wishes to know whether a message has been received at a receiving node and is unconcerned with how many copies of the message did not get through, so long as one does get through.
Attributes of an N by N crossbar switch are as follows:
1. Connection allocation and deallocation requests must be able to arrive from sources and sinks in an uncorrelated manner. Sources must be able to generate connection allocation requests and once a connection is established, either the source or the sink should be free to terminate the connection. Multiple connections should be handled concurrently. Sources and sinks should not be required to wait several clock cycles for a connection request to be completed. PA1 2. The architecture must scale to encompass any size crossbar switch. Although physical constraints will limit the ultimate scalability of any design, the architecture itself should not impose any physical limits. PA1 3. The crossbar switch architecture must be able to perform in a pipeline manner. PA1 4. The crossbar switch architecture should not require an alternate connection control path, but rather should employ the primary data path for both data and control signal transmission. In other words, connection allocation should be performed by signals transmitted over the primary data path. PA1 5. The crossbar switch architecture should support both one to one communication between a source and sink and one to many communication between a source and a set of sinks.
The prior art has attempted to achieve the above objectives through a number of design architectures. Several commercial digital crossbar switches provide data routing functions that are controlled by a configuration map. Examples of such switches are the Texas Instruments 74ACT8841 and 74AS8840. The configuration maps in those switches store connection information that details which sources are connected to which sinks. When a connection allocation or deallocation request is processed, the configuration map must be reloaded. This task is handled by a centralized controller that is implemented by the designer. Map reload takes several clock cycles in most implementations and, as a result, slows the data communication function.
In general, a centralized controller and data routing chip is expensive to implement and does not lend itself well to a dynamic switching environment where allocation and deallocation requests are received in an uncorrelated manner. While multiple crossbar switches can be cascaded to build larger switches, centralized controllers are not easily scalable.
In U.S. Pat. No. 4,852,083 to Niehaus et al., entitled "Digital Crossbar Switch" a crossbar switch is disclosed wherein the state of the switch is stored in a distributed fashion throughout the switch. This switch employs a configuration map which is reloaded, one multiplexer at a time, in order to change any single multiplexer's operation within the crossbar. A plurality of multiplexer logic units both store the relevant portions of the configuration map and enable interconnections to occur. A centralized controller is employed to reconfigure the switch.
U.S. Pat. No. 4,973,956 to Lin et al., entitled "Crossbar Switch With Distributed Memory" illustrates the use of a crosspoint network in a crossbar switch environment. The state of each crosspoint is stored at the crosspoint and is altered by either serially reloading each crosspoint with a new state or by serially reloading succeeding columns of the crosspoint switch under control of column addresses. The technique used to load a new map involves the use of an input data line, and further requires that data transfers be interrupted to enable entry of the new states, after which, data transfers can continue.
U.S. Pat. No. 4,599,721 to Murray, entitled "Programmable Cross Bar Multiplexer" describes a crossbar multiplexer, used as a data routing element, which allows one source to connect to many sinks or multisources to one sink. The multiplexer connection is configured by distributed state indications, however, little is said as to how the state indications are loaded, altered or reloaded.
U.S. Pat. No. 4,929,940 to Franaszek et al., entitled "Collision Crossbar Switch" describes a crossbar network wherein contention detection is employed at the destination. In the event of a collision of messages, rerouting to an alternate path is provided by a second interconnection network which has itself, contention resolution capability. The controller which establishes the initial interconnections in the multiplexer network is not considered in this patent.
A number of patents show the use of centralized controllers for control of crossbar switch states. See U.S. Pat. Nos. 4,975,901 to Poli; 4,929,939 to Varma et al; and European Patent Application 0 315 550 to Petzinger et al. Many other patents describe the use of crossbar switches with various systems but do not specifically describe how the crossbar is itself configured. Such disclosures can be found in European Patent Application 0 356 110 to Peters; 4,633,386 to Terapin; 4,968,977 to Chinnaswamy et al; 4,845,722 to Kent et al., 4,075,693 to Fox et al.,; 4,901,305 to Tangonan; 4,849,751 to Barber et al.; and in the following IBM Technical Disclosure Bulletin Articles: "Sample Parallel Adapter For A Logic Simulation Machine" Miranker, Vol. 25, No. 3A August 1982, pages 1274-1275, and "Data/Test-Controlled Memory Architecture for Supercomputers", Chang et al., Volume 28, No. 3, August 1985 pages 1293-1295.
Accordingly, it is an object of this invention to provide an improved crossbar switch that is adapted to handle allocation and deallocation requests that arrive in an uncorrelated manner.
It is another object of this invention to provide an improved crossbar switch whose state and control are distributed throughout the crossbar switch.
It is still another object of this invention to provide an improved crossbar switch architecture wherein control and data signals are transmitted over common paths.
It is yet another object of this invention to provide an improved crossbar switch architecture which has the ability to support one-to-one communication between a source and a sink, and one to many communication between a source and set of sinks.